package com.tucc.hello.leetcode.no1_400.no1_200.no41_60.no47;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 1, 1, 2};
        System.out.println(solution.permuteUnique(nums));
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (nums.length > 0) {
//            Arrays.sort(nums);
            permute(nums, nums.length, new ArrayList<>(), resultList);
        }
        return resultList;
    }


    public void permute(int[] nums, int size, List<Integer> result, List<List<Integer>> resultList) {
        if (size == 0) {
            resultList.add(new ArrayList<>(result));
        } else {
            Set<Integer> used = new HashSet<>();
            for (int i = 0; i < size; i++) {
                if(used.add(nums[i])) {
                    result.add(nums[i]);
                    swap(nums, i, size - 1);
                    permute(nums, size - 1, result, resultList);
                    swap(nums, i, size - 1);
                    result.remove(result.size() - 1);
                }
            }
        }
    }

    public void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}
